1. Field of the Invention
The invention relates to telecommunications networking. More particularly, the invention relates to an algorithm for selecting middle stage switch elements when setting up a connection in a Clos network.
2. State of the Art
There are two types of telecommunications networks: packet networks and switched networks. In a packet network there is no direct connection between a sender and a receiver. All users of a packet network have an address and information is transferred among users in packets which contain the address of the receiver. In a switched network, a discrete physical connection is established between network users and information flows between users in a stream. The earliest switched networks were the Bell Telephone System and others like it, now known as the public switched telephone network (PSTN). One of the earliest devices for automatically connecting (network switching) one telephone user to another telephone user is known as the crossbar switch.
A crossbar switch has a plurality of vertical paths and a plurality of horizontal paths with a switch (e.g. a relay) at each crossing point such that any one of the vertical paths can be connected to any one of the horizontal paths. Crossbar switches are still very much in use today although the new crossbar switches are microelectronic rather than electromechanical like the original crossbar switches. In a network having many users, crossbar switches are interconnected in stages to form a matrix where there are middle switch elements and end switch elements. The end switch elements are usually referred to as input switch elements and output switch elements. Such a network of interconnected crossbar switches is usually called a “Clos” network, named after the Bell Systems engineer who proposed a non-blocking network of crossbar switches. See, Clos, C., “A Study of Non-blocking Switching Networks”, Bell Systems Technical Journal, Vol. 32, pp. 406-424, March 1953. The Clos network architecture is still in use today in modern optical networks and in wireless networks.
A simplified three stage Clos network is illustrated in prior art FIG. 1. The network shown in FIG. 1 has four input stage switch elements, each having 3×3 ports, four output stage switch elements, each having 3×3 ports, and three middle stage switch elements each having 4×4 ports. In a real network, the number of ports and the number of switch elements would be much larger. It is also common to have a network switch with more than three stages. However, the general architecture of a three stage Clos network having an equal number of input and output ports can be expressed as: r number of n×m input stage switch elements, m number of r×r middle stage switch elements and r number of m×n output stage switch elements. In this arrangement, there is exactly one link between every two switch elements in consecutive stages. The general notation for such a network is v(m,n,r). For a given n and r, varying the number m will alter the connecting capability of the network. From FIG. 1, it will be appreciated that there can easily arise a condition where one of the input switch elements cannot be connected to a desired output switch element. For example, if input switch 1 selects middle switch 1 to connect to output switch 2 and any one or more input switch elements use middle switch elements 2 and 3 to connect to output switch element 1, there is no path available for input switch element 1 to connect to output switch element 1. It will also be appreciated that, with prescience, the middle switch elements could be selected in such a way that blocking of connections is minimized.
Clos showed that a v(m,n,r) network is “strictly non-blocking” if the number of middle stage switch elements m≧2n−1. If the network satisfies this condition, any middle switch element may be chosen arbitrarily to make a connection without blocking the switch. A strictly non-blocking network requires either “overbuild” of the middle stages or idle ports on the input and output stages. It is, therefore, an inefficient use of hardware.
Benes showed that a v(m,n,r) network is “rearrangeable” if the number of middle switch elements m≧n. See, Benes, V. E., “The Mathematical Theory of Connecting Networks and Telephone Traffic”, Academic Press New York, 1965. If the network satisfies this condition, a connection request can always be met but it may require rearrangement of an existing connection in the network. However, rearrangement disrupts the existing connection and delays the requested connection for “path routing”.
Benes proposed an intelligent routing control strategy as a compromise between “strictly non-blocking” and “rearrangeable” networks. A network is called “wide-sense non-blocking” if the number of middle switch elements m satisfies 2n−1≧m≧n and a routing algorithm (“strategy”) is employed. Different strategies require different numbers of middle stage switch elements. A commonly used control strategy for wide-sense non-blocking networks is known as “packing” strategy. A wide-sense non-blocking network using packing strategy is also known as “semi-rearrangeably non-blocking”.
Under packing strategy, a connection is realized on a path found by trying the most used part of the network first and the least used part last. For a v(m; n; r) network, this means that when choosing a middle switch for satisfying a connection request, an empty middle switch is not used unless there is not any partially filled middle switch that can satisfy this connection request. Packing strategy can also be combined with “repacking”.
Repacking means when a connection is released one or more existing connections are moved to the most used part of the network. Repacking is essentially a type of rearrangement although the rearrangement is performed at the time a connection is released not at the time a connection is established. It is generally believed that packing/repacking can improve network performance and reduce network cost.
Packing and repacking algorithms can be even more complicated where a time division multiplexed (TDM) signal enters an input port and is demultiplexed at the input switch element such that different time slots are directed to different output ports through different middle stage switch elements. The algorithms are further complicated by multi-rate versus single rate connections.
Ohta proposed a simple control algorithm (SCA) which is semi-rearrangeable in the sense that only a single connection is rearranged upon a disconnect for single rate connections, while following a path hunt algorithm at connection setup. See, Ohta S, “A Simple Control Algorithm for Rearrangeable Switching Networks with TDM links”, IEEE JSAC, Vol. SAC-5, No. 8, October 1987. The key factor regarding the SCA, and other similar algorithms is the required expansion in the middle stage of the network or idle ports at the input and output stages to achieve non-blocking operation. In either case network capacity is less than full, i.e. in no case are all of the ports and all of the switch paths active.
In Ohta's control algorithm, C(I, J, K) denotes the number of active connections (or time slots) for each respective link in the case of single rate connections, between first stage input switch I, third stage output switch J, and middle stage switch element K. The control algorithm requires that:
1. On connection request, a middle stage switch element K is selected such that C(I, J, K)=minp C(I, J, p);
2. On disconnect of a connection between (I, J) through middle stage switch element K, and given C(I, J, K), do not execute re-arrangement if C(I, J, K) is equal to maxp C(I, J, p) before the disconnect. Otherwise rearrange a connection C(I, J, K′) that satisfies C(I, J, K′)=maxp C(I, J, p).
This algorithm has also been applied to multi-rate connections. The range of switch capacity for which the SCA algorithm is non-blocking has been derived and mathematically proven. The algorithm is particularly limited for the multi-rate applications, especially when the ratio between the lowest and the highest rate connections is large. In typical networks this ratio is several hundred and thus further reduces the range of network capacities for which the semi-rearrangeable algorithm is operationally useful. See, Liotopoulos, F. K., Chalasani, S., “Semi—rearrangeably Non-blocking Operation of Clos Networks in the Multirate Environment,” IEEE/ACM Trans. on Networking, Vol. 4, No. 2, April 1996.
The SCA is a distributed algorithm in the sense that each input stage switch element only requires knowledge of two parameters:
(a) C(I, J, K)—the number of connections or timeslots from first stage switch element I, to third stage switch element J, through switch element K (required to determine minp C(I, J, p)); and
(b)       ∑          ∀                           ⁢      I        ⁢      C    ⁡          (              I        ,        J        ,        K            )      —the sum of C(I, J, K) values for all first stage switch elements (required to determine if a middle stage switch element K has a free slot to set-up a connection between (I, J) through middle stage switch element K.
Typically, the parameter described in (a) is locally available to each input stage switch element individually, while the parameter described in (b) reflects the status of a remote shared resource, e.g. the output port capacity of a middle stage switch element. The parameter in (b) can be discovered in one of two ways: through an explicit distribution mechanism, or by implicit connection attempts. In the latter case an input switch element simply attempts to make a connection through a sequence of middle stage switches, until it succeeds. However, the sequence in which these attempts are made is determined by the SCA algorithm, and independently for each input stage switch element.
The disadvantages of the prior art can be summarized as follows. No state of the art algorithm makes full use of the network while providing non-blocking operation. Although some algorithms can be implemented in a distributed fashion, not all can. The state of the art algorithms do not work well setting up large ratio multi-rate connections.